package com.beautiful.xin.sort;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * @author xuqingxin 2021/7/6 7:33 下午
 */
public class HeapSort {

    public static void main(String[] args) {

        int[] arr = {4, 6, 8, 5, 9};
        //heapSort(arr);
        //int k = findKth(arr,5,3);
        //System.out.println(k);
        //LinkedList<Integer> ll = new LinkedList<>();
        //ll.add(1);
        //
        //ll.add(2);
        //
        //System.out.println(ll.pop());
        //System.out.println(ll.pop());
        //System.out.println("=====");
        //ll.push(3);
        //
        //ll.push(4);
        //System.out.println(ll.pollLast());
        //System.out.println(ll.pollLast());
        //System.out.println(ll);H
        boolean asddsa = judge("asddsa");
        System.out.println(asddsa);
    }
    public static boolean judge (String str) {
        // write code here
        if(str.length() ==1) return true;
        for(int i = 0; i<str.length() ;i++){
            char c = str.charAt(i);
            char c1 = str.charAt(str.length() - 1 - i);
            return  c==c1 ;
        }
        return false;
    }
    public static void heapSort(int[] arr) {
        System.out.println("堆排序");
        //adjustHeap(arr,1,arr.length);
        //System.out.println(Arrays.toString(arr));
        //
        //adjustHeap(arr,0,arr.length);
        //System.out.println(Arrays.toString(arr));

        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; j--) {
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;

            adjustHeap(arr, 0, j);
        }

        System.out.println(Arrays.toString(arr));

    }

    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];

        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }


    public static void hs(int[] arr) {

        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            hs(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; j--) {
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;
            hs(arr, 0, j);
        }
    }

    private static void hs(int[] arr, int i, int length) {
        int temp = arr[i];

        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            if (k < length - 1 && arr[k] < arr[k + 1]) {
                k++;
            }
            if (arr[k] > temp) {
                temp = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    public static int findKth(int[] a, int n, int K) {
        // write code here
        if(n<K) return -1;
        for(int i = n/2-1;i>=0;i--){
            heapSort(a, i, n);
        }
        int c = 1;
        for(int j = n-1;j>=0 ;j--){
            int temp = a[j];
            a[j] = a[0];
            a[0] = temp;
            if(c == K){
                return a[j];
            }
            c++;
            heapSort(a,0,j);
        }
        return -1;
    }
    public static void heapSort(int[] arr, int i , int length){
        int temp = arr[i];
        for(int k = 2*i+1;k<length;k = 2* k+1){
            if(k+1<length&&arr[k]<arr[k+1]){
                k++;
            }
            if(arr[k]>temp){
                arr[i]=arr[k];
                i=k;
            }else{
                break;
            }
        }
        arr[i]=temp;
    }
}
